1. Field of the Invention
This invention relates to arrangements for route control for routing communications traffic in computer networks. More specifically, the invention relates to arrangements employing logically centralized but physically distributed servers, distinct from network routers, to provide scalable and fine-grained route control.
2. Background Art
Given the best-effort communication model of the Internet, Internet routing has historically been purely concerned with connectivity, that is, finding a loop-free shortest path between Internet endpoints. Deviations from this default behavior normally involved policy changes at fairly slow time-scales to effect business and network management objectives. Further, within a particular network or autonomous system (AS), routing was realized by a fixed and fairly simple decision process designed to ensure consistent decision making between the routers in the network.
As networked applications and traffic engineering techniques have evolved, however, they have placed increasingly sophisticated demands on the routing infrastructure. For example, applications such as voice over Internet protocol (VoIP) and online gaming can be very sensitive to the characteristics of the chosen data path. Numerous studies have shown non-default Internet paths can often provide improved performance characteristics as compared to routing approaches that are not aware of network conditions.
Additionally, today's operators are often required to restrict the “any-to-any” connectivity model of the Internet to deal with unwanted traffic in the form of distributed denial of service (DDoS) attacks. Responses can take the form of black-holing traffic, redirecting it to scrubbing complexes, or even more sophisticated differentiation of unwanted traffic based on network intelligence.
Finally, in some cases the default border gateway protocol (BGP) decision process is simply at odds with provider and/or customer goals. For example (see Jacobus E. van der Merwe et al. “Dynamic Connectivity Management with an Intelligent Route Service Control Point,” ACM SIGCOMM INM, October 2006), using interior gateway protocol (IGP) cost as a tie breaker in the decision process can lead to unbalanced egress links for customers that are multi-homed to a provider.
These demands demonstrate a need in the art for route control that is fine-grained, informed by external information, and applied at time-scales much shorter than normal routing configuration changes. Unfortunately, BGP does not provide adequate means for performing fine-grained route control. BGP's tuning parameters are both arcane and indirect. Operators are forced to tweak BGP attributes in cumbersome, vendor-specific router configuration languages at a low level of abstraction, frequently leading to ineffective or, worse, incorrect route selections.
Given this scenario, routing and forwarding in typical Internet service provider (ISP) networks may be described in the following way. We specifically consider the role played by border gateway protocol (BGP), interior gateway protocol (IGP) and multi protocol label switching (MPLS), and describe BGP's default route selection process.
FIG. 1A shows a simplified view of the physical infrastructure of a typical ISP. The routers at the periphery of the ISP 100 network connect to customers 120 and other ISPs 110 (called peers). These routers are termed as Provider Edge (PE) routers (PERs), and the routers that interconnect the PERs are called Provider Core (PC) routers (PCRs). The customer routers connecting to PERs are called Customer Edge (CE) routers (CERs). BGP allows an ISP to learn about destinations reachable through its customers and through its peers.
Typically, every PER runs BGP sessions with its attached CERs, and also with other PERs in the ISP network. The former are known as exterior border gateway protocol (eBGP) sessions, while the latter are termed interior border gateway protocol (iBGP) sessions. The eBGP and iBGP sessions are shown, respectively, as light dashed lines and heavy dashed lines in FIG. 1B.
When a PER learns a route over its eBGP session, it propagates the route to other PERs over the iBGP sessions. This propagation allows every PER to learn how to reach every customer network. When a data packet arrives at a PER for a given customer, an ingress PER uses a BGP routing table to determine an egress PER that is connected to the destination customer, and forwards the packet to this PER. This process is depicted in FIG. 1C. Since the packet leaves ISP network at the PER directly connected to the customer, it is called an egress PER and its link to the CER an egress link.
The path between ingress and egress router is determined by another routing protocol known as an interior gateway protocol (IGP). Open Shortest Path First (OSPF) and Intermediate system to intermediate system (IS-IS), are two widely used IGPs.
IGPs determine a path between every PER pair. Thus, when a packet traverses from ingress PER to egress PER, the set of P routers it goes through is determined by the IGP running in the ISP network 100. In an MPLS network (or indeed any network that utilizes tunneling technologies), when the packet goes through P routers, the P routers are not aware of the ultimate destination of the packet. They only know that the packet is going to the egress PER. This operation is achieved by setting up “tunnels” between every pair of PERs in ISP networks (see FIG. 1B), and by prepending information about tunnel end-point (egress PER) to the packet. This obviates the need of running BGP on the P routers since they are only tunneling packets to the egress PER encoded in the packet.
A PER usually receives more than one egress route for a given destination. Accordingly, the PER must run a route selection algorithm called a BGP decision process to select the best route to use for data forwarding. A BGP decision process is shown in FIG. 2A.
Referring to FIG. 2A, starting with the set of routes available to the PER, each step compares a new route with previously received routes to determine the best route. At each step, if the condition holds, the process is completed and the “winning” route is selected. Steps 201-204 compare routes in terms of the BGP attributes attached to the routes, while steps 200 and 205 consider the IGP information associated with the egress PER of the route.
Steps 205 and 206 perform what is loosely called hot-potato routing. Hot-potato routing involves forwarding traffic to the “nearest” (in terms of IGP distance) egress PER. Step 207 is a tie-breaker that ensures that the PER always ends up with a single best route. The PER uses the best route to forward traffic and also sends this route to other PERs and CERs.
FIGS. 1A-1C show a specific problem introduced by the known process of hot-potato routing as an exemplary illustration of the lack of fine grained route control characteristic of the default BGP decision process in FIG. 2A. Assume for this example that the dual connectivity (CER X and CER Y) of the customer network 120 to the provider network 100 (PER 5 and CER 4) is for redundancy reasons so that the same destinations are reachable via both links. All PERs in provider network 100 therefore have two possible routes to reach the customer network. Assume further that most of the traffic destined to the customer network enter the provider network from the peering ISP network.
Assuming unit IGP costs for each internal provider link, PER 1 and PER 2 both prefer the route via PER 5 connected with the customer network. This preference leads to a complete imbalance in the traffic load on the two egress links, with PER 5's egress link carrying all (or most) of the traffic (FIG. 1C).
Thus, there is a need in the art for a more desirable solution. The present inventors have recognized that the solution may be enabled by fine-grained route control, and that load on the two egress links from PER 4 and PER 5 could be balanced by basing the route selection process for the ingress routers on a load balancing algorithm that takes into account both the “offered” ingress load, as well as the load on the egress links where load balancing is desired.
While it is possible in principle to overcome this specific problem using BGP mechanisms, the required configuration changes would be both complicated and fragile. For example, a system could be devised to provide the appropriate ingress policy rules on all edge routers so that routes from the appropriate egress link gets assigned with a higher localpref value so that (in that router) it is preferred over other routes. However, since localpref is an attribute with network wide scope, localpref would have to be reset before the route is advertised to other routers to prevent interference with their selection process.
Earlier work on route servers (D. Haskin, “A BGP/IDRP Route Server alternative to a full mesh routing,” IETF RFC 1863, October 1995) proposed changes to the way routes were distributed between routers, but specifically did not envision any route selection to be performed in these servers. Later eBGP-speaking route servers (Ramesh Govindan, Cengiz Alaettinoglu, Kannan Varadhan, and Deborah Estrin, “Route Servers for Inter-Domain Routing,” J. Comp. Net. ISDN Sys., 30:1157-1174, 1998.) similarly addressed the full-meshed connectivity problem between eBGP speakers (typically in Internet exchange points). Another approach proposed to the IETF more sophisticated route reflectors (O. Bonaventure, S. Uhlig, and B. Quoitin, “The Case for More Versatile BGP Route Reflectors,” draft-bonaventure-bgp-route-reflectors-00.txt, July 2004.); the authors described a number of potential applications but restricted their proposal to changes to the iBGP infrastructure. More recently a complete refactoring of the network architecture in the 4D project also proposed a logically centralized control plane that is separated from the forwarding elements (Albert Greenberg, Gisli Hjalmtysson, David A. Maltz, Andy Myers, Jennifer Rexford, Geoffrey Xie, Hong Yan, Jibin Zhan, and Hui Zhang, “A clean slate 4D approach to network control and management,” SIGCOMM CCR, 35(5), 2005).
Another IETF proposal on changes to the BGP route selection process is similar to an egress ranking functionality (Cisco Systems, “BGP cost community,” Cisco IOS Documentation; and Alvaro Retana and Russ White, “Bgp custom decision process,” draft-retana-bgp-custom-decision-00.txt, April 2003). The proposal defines a new extended BGP community, the cost community, which can be assigned to routes and then be used to break ties at a certain “points of insertion” in the BGP decision process. Their proposal does not indicate under what conditions the cost community would be safe to use and thus there is a need to show how rankings should be constrained to ensure correctness (for example, no deflections or looping; see FIGS. 4C, 4D).
The inadequacies of hot-potato routing are also addressed in (Renata Teixeira, Timothy G. Griffin, Mauricio G. C. Resende, and Jennifer Rexford, “TIE breaking:l Tunable inter-domain egress selection,” In CoNEXT, 2005.). The authors propose a TIE ranking metric, which allows operators to trade off reacting to network changes (like hot-potato routing does) versus a more static ranking, which might be designed to favor specific applications or services. Further, T. C. Bressoud, R. Rastogi, and M. A. Smith, “Optimal configuration for BGP route selection,” IEEE INFOCOM, March 2003, considers the optimal assignment of routes to routers to satisfy both traffic engineering and capacity constraints. However, neither of these works fully deal with realization options, and thus the needs in the art mentioned above, remain unfulfilled.